#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

#define Max_Size 20
#define ElementType int

struct Array
{
    int arr[Max_Size];
    int len;
};
typedef struct Array Arr;

void InitArray(Arr *a)
{
    memset(&a->arr, 0, Max_Size);
    a->len = 0;
}

bool InsertTail(Arr *a, ElementType value)
{
    if (a->len >= Max_Size)
    {
        printf("顺序表容量已满！插入失败");
        return false;
    }
    a->arr[a->len++] = value;
    return true;
}

bool InsertHead(Arr *a, ElementType value)
{
    if (a->len >= Max_Size)
    {
        printf("顺序表容量已满！插入失败");
        return false;
    }
    for (int i = a->len; i > 0; i--)
    {
        a->arr[i] = a->arr[i-1];
    }
    a->arr[0] = value;
    a->len++;
}

bool InsertByIndex(Arr *a, int index, ElementType value)
{
    if (a->len >= Max_Size)
    {
        printf("顺序表容量已满！插入失败");
        return false;
    }
    if (index < 0 || index > a->len)
    {
        printf("非法位置插入！\n");
        return false;
    }
    for (int i = a->len; i > index; i--)
    {
        a->arr[i] = a->arr[i-1];
    }
    a->arr[index] = value;
    a->len++;
    return true;
}

bool UpdateValueByIndex(Arr *a, int index, ElementType value)
{
    if (index < 0 || index > a->len)
    {
        printf("非法位置修改！\n");
        return false;
    }
    a->arr[index] = value;
    return true;
}

bool UpdateValueByElement(Arr *a, ElementType oldValue, ElementType newValue)
{
    for (int i = 0; i < a->len; i++)
    {
        if (a->arr[i] == oldValue)
        {
            a->arr[i] = newValue;
        }
    }
    return true;
}

bool RemoveByIndex(Arr *a, int index)
{
    if (index < 0 || index > a->len)
    {
        printf("非法位置删除！\n");
        return false;
    }
    for (int i = index; i < a->len - 1; i++)
    {
        a->arr[i] = a->arr[i+1];
    }
    a->len--;
    return true;
}

bool RemoveByElement(Arr *a, ElementType value)
{
    for (int i = 0; i < a->len; i++)
    {
        if (a->arr[i] == value)
        {
            RemoveByIndex(a, i);
            i--;
        }
    }
    return true;
}

ElementType* FindElementByIndex(Arr *a, int index)
{
    if (index < 0 || index > a->len)
    {
        printf("非法位置查找！\n");
        return NULL;
    }
    return &a->arr[index];
}

int* FindElementByValue(Arr *a, ElementType value)
{
    int *p = (int *)malloc(a->len+1);
    if (a == NULL)
    {
        printf("FindElementByValue malloc error\n");
        return NULL;
    }
    // 在第一个位置存下数量
    // int count = 0;
    // for (int i = 0; i < a->len; i++)
    // {
    //     if (a->arr[i] == value)
    //     {
    //         count++;
    //         // 将下标存到数组中
    //         p[count] = i;
    //     }
    // }
    // // 第一个位置存的是找到的数量
    // p[0] = count;

    // 在最后一个位置放上-1终止符
    int count = 0;
    for (int i = 0; i < a->len; i++)
    {
        if (a->arr[i] == value)
        {
            // 将下标存到数组中
            p[count] = i;
            count++;
        }
    }
    // 第一个位置存的是找到的数量
    p[count] = -1;
    return p;
}

void ArraySort(Arr *a, int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int left = start;
    int right = end;
    int temp = a->arr[left];
    while (left < right)
    {
        while(a->arr[right] > temp && left < right)
        {
            right--;
        }
        a->arr[left++] = a->arr[right];
        
        while(a->arr[left] < temp && left < right)
        {
            left++;
        }
        a->arr[right--] = a->arr[left];

        a->arr[left] = temp;
    }
    ArraySort(a, start, left-1);
    ArraySort(a, right+1, end);
}

Arr GetInsection(Arr *a1, Arr *a2)
{
    Arr c;
    InitArray(&c);

    for (int i = 0; i < a1->len; i++)
    {
        for (int j = 0; j < a2->len; j++)
        {
            if (a1->arr[i] == a2->arr[j])
            {
                int *a = FindElementByValue(&c, a1->arr[i]);
                if (a == NULL || a[0] == -1)
                {
                    InsertTail(&c, a1->arr[i]);
                }
                if (a != NULL)
                {
                    free(a);
                }
            }
        }
    }
    return c;
}

void Deduplicate(Arr *a)
{
    ArraySort(a, 0, a->len-1);
    for (int i = 1; i < a->len; i++)
    {
        if (a->arr[i] == a->arr[i-1])
        {
            RemoveByIndex(a, i);
            i--;
        }
    }
}

Arr GetUnionSet(Arr *a1, Arr *a2)
{
    Arr UnionSet;
    InitArray(&UnionSet);
    for (int i = 0; i < a1->len; i++)
    {
        InsertTail(&UnionSet, a1->arr[i]);
    }
    for (int i = 0; i < a2->len; i++)
    {
        InsertTail(&UnionSet, a2->arr[i]);
    }
    Deduplicate(&UnionSet);
    return UnionSet;
}

Arr Merge(Arr *a1, Arr *a2)
{
    ArraySort(a1, 0, a1->len-1);
    ArraySort(a2, 0, a2->len-1);
    int i = 0, j = 0;
    Arr result;
    InitArray(&result);
    while (i < a1->len && j < a2->len)
    {
        if (a1->arr[i] <= a2->arr[j])
        {
            InsertTail(&result, a1->arr[i]);
            i++;
        }
        else
        {
            InsertTail(&result, a2->arr[j]);
            j++;
        }
    }
    for (int k = i; k < a1->len; k++)
    {
        InsertTail(&result, a1->arr[k]);
    }
    for (int k = i; k < a2->len; k++)
    {
        InsertTail(&result, a2->arr[k]);
    }
    return result;
}

int BinarySearch(Arr *a, ElementType value)
{
    int start = 0;
    int end = a->len - 1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (a->arr[mid] == value)
        {
            return mid;
        }
        else if (a->arr[mid] > value)
        {
            end = mid - 1;
        }
        else 
        {
            start = mid + 1;
        }
    }
    return -1;
}

void print(Arr *a)
{
    for (int i = 0; i < a->len; i++)
    {
        printf("%d ", a->arr[i]);
    }
    printf("\n");
}

int main()
{
    Arr a;
    InitArray(&a);
    for (int i = 0; i < 5; i++)
    {
        InsertTail(&a, i+1);
    }
    print(&a);

    for (int i = 0; i < 5; i++)
    {
        InsertHead(&a, i+1);
    }
    print(&a);

    // InsertByIndex(&a, 5, 100);
    // print(&a);

    // UpdateValueByIndex(&a, 5, 200);
    // print(&a);

    // UpdateValueByElement(&a, 1, 11);
    // print(&a);

    // RemoveByIndex(&a, 5);
    // print(&a);
    
    // RemoveByElement(&a, 11);
    // print(&a);

    // ElementType *value = FindElementByIndex(&a, 4);
    // if (value == NULL)
    // {
    //     printf("没找到\n");
    // }
    // else
    // {
    //     printf("找到了：%d\n", *value);
    // }

    // int *p = FindElementByValue(&a, 4);
    // if (p != NULL)
    // {
    //     // for (int i = 1; i <= p[0]; i++)
    //     // {
    //     //     printf("%d ", p[i]);
    //     // }
    //     int i = 0;
    //     while (p[i] != -1)
    //     {
    //         printf("%d ", p[i++]);
    //     }
    //     printf("\n");
    // }

    ArraySort(&a, 0, a.len-1);
    print(&a);

    Arr b;
    InitArray(&b);
    for (int i = 0; i < 10; i+= 2)
    {
        InsertHead(&b, i+1);
    }
    print(&b);

    Arr c = GetInsection(&a, &b);
    print(&c);

    Arr d = GetUnionSet(&a, &b);
    print(&d);

    Arr e = Merge(&a, &b);
    print(&e);

    printf("%d\n", BinarySearch(&e, 4));

    return 0;
}